class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        k = Math.min(k, n / 2);
        // 状态表示 - 第 i 天，第 j 次交易，处于买入/卖出状态时获得的最大利润
        int[][] f = new int[n][k + 1]; // 买入状态
        int[][] g = new int[n][k + 1]; // 卖出状态
        // 初始化
        int INF = 0x3f3f3f3f;
        for(int j = 0; j <= k; j++){
            f[0][j] = -INF;
            g[0][j] = -INF;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        // 状态转移方程
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0)
                    g[i][j] = Math.max(f[i - 1][j - 1] + prices[i], g[i - 1][j]);
            }
        }
        int ret = -INF;
        for(int j = 0; j <= k; j++) ret = Math.max(ret, g[n - 1][j]);
        return ret;
    }
}